package com.wyp168.leetcode.bfs;

/**
 * @ClassName BestCoordinateSolution
 * @Title TODO
 * @Description TODO
 * @Author wyp168
 * @Date 2022/11/2 00:03
 */
public class BestCoordinateSolution {
    public static void main(String[] args) {
        BestCoordinateSolution bestCoordinateSolution = new BestCoordinateSolution();
        int[][] towers = {{1,2,15},{2,1,7}, {0,1,9}};
        int radius = 2;
        int[] ints = bestCoordinateSolution.bestCoordinate(towers, radius);
        System.out.println(ints[0] + "," + ints[1]);
    }
    public static final int[][] dest = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int[] bestCoordinate(int[][] towers, int radius) {
        //定义表示坐标的数组


        int[][] isDone = new int[2 * radius + 1][2 * radius + 1];
        int[] flagDoneIndex = {radius, radius};
        isDone[radius][radius] = 1;

        int[] resultIndex = {0, 0, 0};

        int[] tempTower = {towers[0][0], towers[0][1]};
        int tempMax;
        //旋转方向的次数
        int flag = 0;
        while (true) {
            tempMax = 0;
            for (int[] tower : towers) {
                double d = Math.sqrt(Math.pow(tower[0] - tempTower[0], 2) + Math.pow(tower[1] - tempTower[1], 2));
                if (d > radius) {
                    tempMax = -1;
                    break;
                }
                tempMax += (int) (tower[2] / (d + 1));
            }
            if (tempMax > resultIndex[2]) {
                resultIndex[0] = tempTower[0];
                resultIndex[1] = tempTower[1];
                resultIndex[2] = tempMax;
            } else if (tempMax == resultIndex[2]) {
                if (tempTower[0] < resultIndex[0] || (tempTower[0] == resultIndex[0] && tempTower[1] < resultIndex[1])) {
                    resultIndex[0] = tempTower[0];
                    resultIndex[1] = tempTower[1];
                }
            }
            //指针移动
            if ((flag = move(flag, flagDoneIndex, isDone, tempTower)) == -1) {
                break;
            }
        }

        return new int[] {resultIndex[0], resultIndex[1]};

    }
    public int move(int flag, int[] flagDoneIndex, int[][] isDone, int[] tempTower) {
        int count = 0;
        while (count < 4) {
            int newX = flagDoneIndex[0] + dest[flag][0];
            int newY = flagDoneIndex[1] + dest[flag][1];
            if (newX < isDone[0].length && newX >= 0 &&
                    newY < isDone.length && newY >= 0 &&
                    isDone[newX][newY] != 1) {
                flagDoneIndex[0] = newX;
                flagDoneIndex[1] = newY;
                tempTower[0] += dest[flag][0];
                isDone[newX][newY] = 1;
                tempTower[1] += dest[flag][1];
                return flag;
            }
            flag = flag + 1 == 4 ? 0 : flag + 1;
            count ++;
        }
        return -1;
    }

}
